package leetcode.code1589;

import java.util.Arrays;

public class Solution {

	int mod = (int) 1e9 + 7;

	public int maxSumRangeQuery(int[] nums, int[][] requests) {
		int n = nums.length;
		int[] arr = new int[n + 1];
		for (int i = 0; i < requests.length; i++) {
			int[] r = requests[i];
			arr[r[0]]++;
			arr[r[1] + 1]--;
		}
		int[] cnts = new int[n];
		for (int i = 0, sum = 0; i < cnts.length; i++) {
			cnts[i] = sum += arr[i];
		}
		Arrays.sort(nums);
		Arrays.sort(cnts);
		long ans = 0;
		for (int i = 0; i < cnts.length; i++) {
			ans = (ans + 1l * nums[i] * cnts[i]) % mod;
		}
		return (int)ans;
	}
}
